package a_doubleWrite;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-31 10:42
 */
public class L212 {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> list = new ArrayList<>();
        for (String s : words) {
            outer:
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    boolean[][] visit = new boolean[board.length][board[0].length];
                    if (dfs(visit, board, 0, s, i, j)) {
                        list.add(s);
                        break outer;
                    }

                }
            }
        }
        return list;
    }

    private boolean dfs(boolean[][] visit, char[][] board, int index, String s, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
                || board[i][j] != s.charAt(index) || visit[i][j]) {
            return false;
        }
        if (index == s.length() - 1) {
            return true;
        }
        visit[i][j] = true;
        boolean flag = dfs(visit, board, index + 1, s, i, j + 1) || dfs(visit, board, index + 1, s, i, j - 1) ||
                dfs(visit, board, index + 1, s, i - 1, j) || dfs(visit, board, index + 1, s, i + 1, j);
        //回溯
        visit[i][j] = false;
        return flag;
    }

    public static void main(String[] args) {
        L212 l212 = new L212();
    }
}
